package utils;

/**
 * @Author ZhangCuirong
 * @Date 2025/8/1 9:18
 * @description:
 */
import datastructure.redblacktree.RedBlackTree;

import java.util.*;
import java.util.concurrent.ThreadLocalRandom;

public class RedBlackTreeRandomTester {
    // 测试次数
    private static final int TEST_COUNT = 100;
    // 每次测试的操作数
    private static final int OPERATIONS_PER_TEST = 1000;
    // 数据范围
    private static final int DATA_RANGE = 10000;
    // 删除操作的概率（0.0-1.0）
    private static final double DELETE_PROBABILITY = 0.3;

    public static void main(String[] args) {
        RedBlackTreeRandomTester tester = new RedBlackTreeRandomTester();
        tester.runTests();
    }

    public void runTests() {
        int passed = 0;
        int failed = 0;

        System.out.println("开始进行 " + TEST_COUNT + " 次红黑树随机测试...");
        System.out.println("每次测试包含 " + OPERATIONS_PER_TEST + " 次操作（插入/删除）");

        for (int testNum = 1; testNum <= TEST_COUNT; testNum++) {
            boolean testResult = runSingleTest(testNum);
            if (testResult) {
                passed++;
            } else {
                failed++;
            }
        }

        System.out.println("\n测试完成:");
        System.out.println("总测试次数: " + TEST_COUNT);
        System.out.println("通过次数: " + passed);
        System.out.println("失败次数: " + failed);
        System.out.println("通过率: " + String.format("%.2f%%", (passed * 100.0) / TEST_COUNT));
    }

    /**
     * 执行单次测试
     */
    private boolean runSingleTest(int testNum) {
        RedBlackTree<Integer> tree = new RedBlackTree<>();
        RedBlackTreeValidator<Integer> validator = new RedBlackTreeValidator<>(tree);
        Set<Integer> elements = new HashSet<>(); // 记录当前树中存在的元素
        Random random = ThreadLocalRandom.current();

        try {
            for (int op = 0; op < OPERATIONS_PER_TEST; op++) {
                // 随机决定是插入还是删除操作
                boolean isDelete = elements.size() > 0 &&
                        random.nextDouble() < DELETE_PROBABILITY;

                if (isDelete) {
                    // 从现有元素中随机选择一个删除
                    Integer[] currentElements = elements.toArray(new Integer[0]);
                    int index = random.nextInt(currentElements.length);
                    Integer value = currentElements[index];

                    tree.delete(value);
                    elements.remove(value);
                } else {
                    // 随机生成一个新元素插入
                    int value;
                    do {
                        value = random.nextInt(DATA_RANGE);
                    } while (elements.contains(value)); // 确保值不重复

                    tree.insert(value);
                    elements.add(value);
                }

                // 每次操作后验证红黑树性质
                if (!validator.isValidRedBlackTree(tree.root)) {
                    System.out.println("测试 " + testNum + " 在第 " + op + " 次操作失败");
                    return false;
                }

                // 验证树中的元素与集合中的元素一致
                if (!verifyElements(tree, elements)) {
                    System.out.println("测试 " + testNum + " 在第 " + op + " 次操作元素验证失败");
                    return false;
                }
            }

            System.out.println("测试 " + testNum + " 成功");
            return true;
        } catch (Exception e) {
            System.out.println("测试 " + testNum + " 抛出异常: " + e.getMessage());
            e.printStackTrace();
            return false;
        }
    }

    /**
     * 验证树中实际元素与预期集合一致
     */
    private boolean verifyElements(RedBlackTree<Integer> tree, Set<Integer> expected) {
        Set<Integer> actual = new HashSet<>();
        collectElements(tree.root, actual, tree.nil);

        if (actual.size() != expected.size()) {
            System.out.println("元素数量不一致: 预期 " + expected.size() + ", 实际 " + actual.size());
            return false;
        }

        for (Integer val : expected) {
            if (!actual.contains(val)) {
                System.out.println("元素 " + val + " 应该存在但实际不存在");
                return false;
            }
        }

        for (Integer val : actual) {
            if (!expected.contains(val)) {
                System.out.println("元素 " + val + " 不应该存在但实际存在");
                return false;
            }
        }

        return true;
    }

    /**
     * 收集树中所有元素
     */
    private void collectElements(RedBlackTree<Integer>.Node node, Set<Integer> elements,
                                 RedBlackTree<Integer>.Node nil) {
        if (node == nil) return;
        elements.add(node.key);
        collectElements(node.left, elements, nil);
        collectElements(node.right, elements, nil);
    }
}
